Back خوارزمية ديكسترا Arabic Deykstra alqoritmi Azerbaijani Алгоритъм на Дейкстра Bulgarian Dijkstrin algoritam BS Algorisme de Dijkstra Catalan Dijkstrův algoritmus Czech Dijkstras algoritme Danish Dijkstra-Algorithmus German Αλγόριθμος του Ντάικστρα Greek Dijkstra's algorithm English

Algorithm Dijkstra

Animeiddiad yn dangos algorithm Dijkstra ar ei waith.

Algorithm Dijkstra (neu algorithm Llwybr Lleiaf Cyntaf Dijkstra)[1] yw algorithm gyfer canfod llwybrau byrraf rhwng fertigau mewn graff. Gall cael ei ddefnyddio, er enghraifft, canfod llwybrau lleiaf mewn rhwydweithiau ffyrdd. Fe’i crëwyd gan y gwyddonydd cyfrifiadurol Edsger W. Dijkstra ym 1956 a’i gyhoeddi tair blynedd yn ddiweddarach.[2][3][4]

Ar gyfer fertig ffynhonnell benodol yn y graff, mae'r algorithm yn dod o hyd i'r llwybr byrraf rhwng y fertig hwnnw a phob un arall,[5] gan gynhyrchu coeden llwybr byrraf. Gellir ei ddefnyddio hefyd ar gyfer dod o hyd i'r llwybrau byrraf o fertig sengl i fertig cyrchfan sengl trwy stopio'r yr algorithm unwaith y bydd y llwybr byrraf i'r fertig cyrchfan wedi'i ganfod. Dyma oedd fersiwn gwreiddiol Dijkstra.[4]

Er enghraifft, os yw nodau'r graff yn cynrychioli dinasoedd a chostau llwybr ymyl yn cynrychioli pellteroedd gyrru rhwng parau o ddinasoedd wedi'u cysylltu gan ffordd uniongyrchol (er symlrwydd, anwybyddu goleuadau coch a rhwystrau eraill), gellir defnyddio algorithm Dijkstra i ddod o hyd i'r llwybr byrraf rhwng un ddinas a'r holl ddinasoedd eraill.

  1. ↑ "OSPF Incremental SPF". Cisco. Archifwyd o'r gwreiddiol ar 2019-04-19. Cyrchwyd 2020-11-03.
  2. ↑ Richards, Hamilton. "Edsger Wybe Dijkstra". A.M. Turing Award. Association for Computing Machinery. Cyrchwyd 16 October 2017. At the Mathematical Centre a major project was building the ARMAC computer. For its official inauguration in 1956, Dijkstra devised a program to solve a problem interesting to a nontechnical audience: Given a network of roads connecting cities, what is the shortest route between two designated cities?
  3. ↑ Frana, Phil (August 2010). "An Interview with Edsger W. Dijkstra". Communications of the ACM 53 (8): 41–47. doi:10.1145/1787234.1787249.
  4. ↑ 4.0 4.1 Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390. http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf.
  5. ↑ Mehlhorn, Kurt; Sanders, Peter (2008). "Chapter 10. Shortest Paths". Algorithms and Data Structures: The Basic Toolbox. Springer. doi:10.1007/978-3-540-77978-0. ISBN 978-3-540-77977-3.
From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Tubidy